๋ฌธ์
๋ฐฑ์ค์์ ์์ฅ ์ต๋ฐฑ์ค์ ์ง๋ ๋ช ๋ ๊ฐ ๊ฒ๋ฆฌ๋งจ๋๋ง์ ํตํด์ ์์ ์ ๋น์๊ฒ ์ ๋ฆฌํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ํ์ ํ๋ค. ๊ฒฌ์ ํ ๊ถ๋ ฅ์ด ์์ด์ง ์ต๋ฐฑ์ค์ ๊ถ๋ ฅ์ ๋งค์ฐ ๋ถ๋นํ๊ฒ ํ์ฌํ๊ณ , ์ฌ์ง์ด๋ ์์ ์ด๋ฆ๋ ๋ฐฑ์ค์๋ก ๋ณ๊ฒฝํ๋ค. ์ด๋ฒ ์ ๊ฑฐ์์๋ ์ต๋ํ ๊ณตํํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ํ์ ํ๋ ค๊ณ ํ๋ค.
๋ฐฑ์ค์๋ N๊ฐ์ ๊ตฌ์ญ์ผ๋ก ๋๋์ด์ ธ ์๊ณ , ๊ตฌ์ญ์ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋ค. ๊ตฌ์ญ์ ๋ ๊ฐ์ ์ ๊ฑฐ๊ตฌ๋ก ๋๋ ์ผ ํ๊ณ , ๊ฐ ๊ตฌ์ญ์ ๋ ์ ๊ฑฐ๊ตฌ ์ค ํ๋์ ํฌํจ๋์ด์ผ ํ๋ค. ์ ๊ฑฐ๊ตฌ๋ ๊ตฌ์ญ์ ์ ์ด๋ ํ๋ ํฌํจํด์ผ ํ๊ณ , ํ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋์ด ์๋ ๊ตฌ์ญ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ๊ตฌ์ญ A์์ ์ธ์ ํ ๊ตฌ์ญ์ ํตํด์ ๊ตฌ์ญ B๋ก ๊ฐ ์ ์์ ๋, ๋ ๊ตฌ์ญ์ ์ฐ๊ฒฐ๋์ด ์๋ค๊ณ ํ๋ค. ์ค๊ฐ์ ํตํ๋ ์ธ์ ํ ๊ตฌ์ญ์ 0๊ฐ ์ด์์ด์ด์ผ ํ๊ณ , ๋ชจ๋ ๊ฐ์ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋ ๊ตฌ์ญ์ด์ด์ผ ํ๋ค.
์๋ ๊ทธ๋ฆผ์ 6๊ฐ์ ๊ตฌ์ญ์ด ์๋ ๊ฒ์ด๊ณ , ์ธ์ ํ ๊ตฌ์ญ์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์๋ค.
์๋๋ ๋ฐฑ์ค์๋ฅผ ๋ ์ ๊ฑฐ๊ตฌ๋ก ๋๋ 4๊ฐ์ง ๋ฐฉ๋ฒ์ด๋ฉฐ, ๊ฐ๋ฅํ ๋ฐฉ๋ฒ๊ณผ ๋ถ๊ฐ๋ฅํ ๋ฐฉ๋ฒ์ ๋ํ ์์์ด๋ค.
๊ฐ๋ฅํ ๋ฐฉ๋ฒ: [1, 3, 4]์ [2, 5, 6]์ผ๋ก ๋๋์ด์ ธ ์๋ค.
๊ฐ๋ฅํ ๋ฐฉ๋ฒ: [1, 2, 3, 4, 6]๊ณผ [5]๋ก ๋๋์ด์ ธ ์๋ค.
๋ถ๊ฐ๋ฅํ ๋ฐฉ๋ฒ: [1, 2, 3, 4]์ [5, 6]์ผ๋ก ๋๋์ด์ ธ ์๋๋ฐ, 5์ 6์ด ์ฐ๊ฒฐ๋์ด ์์ง ์๋ค.
๋ถ๊ฐ๋ฅํ ๋ฐฉ๋ฒ: ๊ฐ ์ ๊ฑฐ๊ตฌ๋ ์ ์ด๋ ํ๋์ ๊ตฌ์ญ์ ํฌํจํด์ผ ํ๋ค.
๊ณตํํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋๊ธฐ ์ํด ๋ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋ ์ธ๊ตฌ์ ์ฐจ์ด๋ฅผ ์ต์๋ก ํ๋ ค๊ณ ํ๋ค. ๋ฐฑ์ค์์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ธ๊ตฌ ์ฐจ์ด์ ์ต์๊ฐ์ ๊ตฌํด๋ณด์.
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ๊ตฌ์ญ์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์ ๊ตฌ์ญ์ ์ธ๊ตฌ๊ฐ 1๋ฒ ๊ตฌ์ญ๋ถํฐ N๋ฒ ๊ตฌ์ญ๊น์ง ์์๋๋ก ์ฃผ์ด์ง๋ค. ์ธ๊ตฌ๋ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด์ ธ ์๋ค.
- ์ ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฐ ๊ตฌ์ญ๊ณผ ์ธ์ ํ ๊ตฌ์ญ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ์ ๋ณด์ ์ฒซ ๋ฒ์งธ ์ ์๋ ๊ทธ ๊ตฌ์ญ๊ณผ ์ธ์ ํ ๊ตฌ์ญ์ ์์ด๊ณ , ์ดํ ์ธ์ ํ ๊ตฌ์ญ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ๋ชจ๋ ๊ฐ์ ์ ์๋ก ๊ตฌ๋ถ๋์ด์ ธ ์๋ค.
- ๊ตฌ์ญ A๊ฐ ๊ตฌ์ญ B์ ์ธ์ ํ๋ฉด ๊ตฌ์ญ B๋ ๊ตฌ์ญ A์ ์ธ์ ํ๋ค. ์ธ์ ํ ๊ตฌ์ญ์ด ์์ ์๋ ์๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ๋ฐฑ์ค์๋ฅผ ๋ ์ ๊ฑฐ๊ตฌ๋ก ๋๋์์ ๋, ๋ ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ ์ฐจ์ด์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ๋ ์ ๊ฑฐ๊ตฌ๋ก ๋๋ ์ ์๋ ๊ฒฝ์ฐ์๋ -1์ ์ถ๋ ฅํ๋ค.
๐ Logic
class Dosi {
ArrayList<Integer>[] dosi;
int[] population;
int[] area;
boolean[] visited;
int size;
int answer = Integer.MAX_VALUE;
}
- ์ ๊ฑฐ๊ตฌ์ ์ ๋ณด๋ฅผ ๋ด๋นํ๋ ํด๋์ค์ด๋ค.
public int searchDivision();
- ์ ๊ฑฐ๊ตฌ ๋ถํ ๋ฉ์๋๋ฅผ ํธ์ถํ๊ณ , ์ต์๊ฐ์ ๋น๊ตํด ์ต์ข ์ ์ผ๋ก ์ถ๋ ฅํด์ผ ํ ๊ฐ์ ๋ฐํํ๋ ํจ์์ด๋ค.
private void dfs(int n);
- ์ฌ๊ท์ ์ผ๋ก ํธ์ถ๋๋ฉด์, ๋ชจ๋ ์ ๊ฑฐ๊ตฌ ๋ถํ ๋ฒ์ DFS๋ฐฉ์์ผ๋ก ์์ ํ์ํ๋ฉฐ ์ ๊ฑฐ๊ตฌ๊ฐ 2๊ฐ๋ก ๋ถํ ๊ฐ๋ฅํ ๊ฒฝ์ฐ์๋ง ์ธ๊ตฌ์ ์ฐจ์ด๋ฅผ ๊ณ์ ์ ๋ฐ์ดํธํ๋ ๋ฉ์๋์ด๋ค.
private void bfs(int idx, int areaN);
- ์ ๊ฑฐ๊ตฌ ๋ถํ ํ, ๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ์ ๋ฐ์ดํธํ๊ธฐ ์ํด BFS ๋ฐฉ์์ผ๋ก ์ํ๋๋ ๋ฉ์๋์ด๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Dosi {
ArrayList<Integer>[] dosi;
int[] population;
int[] area;
boolean[] visited;
int size;
int answer = Integer.MAX_VALUE;
public Dosi(int N) {
dosi = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
dosi[i] = new ArrayList<>();
}
area = new int[N + 1];
size = N;
}
public int searchDivision() {
dfs(1);
if (answer == Integer.MAX_VALUE) return -1;
return answer;
}
private void dfs(int n) {
if (n == size + 1) {
int pop1=0, pop2=0;
for (int i = 1; i <= size; i++) {
if (area[i] == 1) pop1 += population[i-1];
else pop2 += population[i-1];
}
visited = new boolean[size + 1];
int cnt = 0;
for (int i = 1; i <= size; i++) {
if (!visited[i]) {
bfs(i, area[i]);
cnt++;
}
}
if (cnt == 2) answer = Math.min(answer, Math.abs(pop1 - pop2));
return;
}
area[n] = 1;
dfs(n + 1);
area[n] = 2;
dfs(n + 1);
}
private void bfs(int idx, int areaN) {
Queue<Integer> q = new LinkedList<>();
visited[idx] = true;
q.add(idx);
while (!q.isEmpty()) {
int now = q.poll();
for(int i = 0; i < dosi[now].size(); i++) {
int next = dosi[now].get(i);
if(area[next] == areaN && !visited[next]) {
q.add(next);
visited[next] = true;
}
}
}
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] line;
Dosi d = new Dosi(N);
d.population = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int i = 0; i < N; i++) {
line = br.readLine().split(" ");
for (int j = 0; j < Integer.parseInt(line[0]); j++) {
d.dosi[i+1].add(Integer.parseInt(line[j+1]));
}
}
System.out.println(d.searchDivision());
br.close();
}
}
โ๏ธ Review
-
๋๋ต์ ์ผ๋ก ๊ตฌ์ํ ๋ฐฉ๋ฒ์,
- ๋ถํ ์ด ๊ฐ๋ฅํ ๋ฐฉ๋ฒ์ผ๋ก ์ ๊ฑฐ๊ตฌ๋ฅผ ๋ ๊ฐ๋ก ๋ถํ
- ๋ถํ ํ ๊ฒฝ์ฐ ์ค, ์ธ๊ตฌ ์ฐจ์ด๋ฅผ ๊ณ์ ์ ๋ฐ์ดํธํ๋ ๋ฐฉ์์ผ๋ก ๊ฐ์ฅ ์ต์๊ฐ ๋๋ ๋ถํ ๋ฒ์ ํ์
-
๊ทธ๋ฐ๋ฐ ์ด๋ป๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ๋ถํ ํด์ผํ๋๊ฐ๊ฐ ๊ณ ๋ฏผ์ด์๋ค. ๊ทธ๋์ ๊ฒ์ํ์์ "0๋ฒ ๊ตฌ์ญ์ด ํฌํจ๋ ์ ๊ฑฐ๊ตฌ vs 0๋ฒ ๊ตฌ์ญ์ด ํฌํจ๋์ง ์์ ์ ๊ฑฐ๊ตฌ" ๋ผ๋ ์์ด๋์ด๋ฅผ ๋ฐ๊ฒฌํด ์๊ฐํด๋ณด์๋ค.
- ์ญ์๋ ๊ตฌํ์์ ๋งํ ์๋ ๋ธ๋ก๊ทธ๋ฅผ ์ฐธ๊ณ ํ๋ค...
-
๋งค๋ฒ ๋ฌธ์ ๋ฅผ ์์ํ ๋ ์ด๋ป๊ฒ ํ๋ฉด ๊น๋ํ๊ฒ ์ ๋ ฅ์ ๋ฐ์ ์ ์ฅํ ์ ์์๊น๋ฅผ ๊ณ ๋ฏผํ๋๋ฐ, ์ด๋ฒ์๋ ์ข ์๋ก์ด ๋ฌธ๋ฒ์ ์ฌ์ฉํด๋ณด์๋ค.
String[] tokens์split(" ")ํ ๊ฒฐ๊ณผ๋ฅผ ๋งค๋ฒ ๋ด์๋ค๊ฐ ์ ์๋ก ํ์ฑํ์ฌ ๋ค์ ์ ์ฅํ๋๋ฐ, ์ด๋ฒ์ ๋ฌธ์์ด ํ ์ค์ ๋ฐ์ ๊ณต๋ฐฑ ๊ธฐ์ค์ผ๋ก ๋๋๋ฉด์ ๋ฐ๋ก ์ ์ํ ๋ฐฐ์ด์ ์ ์ฅํ๋ ๋ฐฉ์์ ์ฌ์ฉํด๋ณด์๋ค.
๐ ์ถ์ฒ
Baekjoon : https://www.acmicpc.net/problem/17471